#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SUB_M		3		// M=6, and SUB_M=M/2

typedef int KEY_VALUE;

typedef struct _btree_node {
	//int keys[2 * SUB_M - 1];					// 存储关键字，M-1
	KEY_VALUE *keys;							// 存储关键字
	// void *value;								// 存储数据
	struct _btree_node **childrens;				// 子树，M
	int num;									// 已存储的key数量
	int leaf;									// 是否为叶子结点
}btree_node;

typedef struct _btree {
	btree_node *root;
	int t;				// M阶，t=M/2
}btree;


btree_node *btree_create_node(int t,int leaf)
{
	btree_node *node = (btree_node *)calloc(1, sizeof(btree_node));
	if (node == NULL)
		return NULL;

	
	node->keys = (KEY_VALUE *)calloc(1, (2 * t - 1)*sizeof(KEY_VALUE));
	if (node->keys == NULL)
	{
		free(node);
		return NULL;
	}
	
	node->childrens = (btree_node **)calloc(1, (2 * t)*sizeof(btree_node*));
	if (node->childrens == NULL)
	{
		free(node->keys);
		free(node);
		return NULL;
	}
	node->leaf = leaf;
	node->num = 0;

	return node;
}

void btree_destroy_node(btree_node *node)
{
	if (node == NULL)
		return;
	if (node->childrens != NULL)
		free(node->childrens);
	if (node->keys != NULL)
		free(node->keys);
	free(node);
}

/**********************分裂 split************************/
// 子节点分裂
void btree_split_child(btree *T, btree_node *x, int idx)
{

	int t = T->t;

	btree_node *y = x->childrens[idx];
	btree_node *z = btree_create_node(t,y->leaf);

	z->num = t - 1;
	int i = 0;
	for (i = 0; i < t - 1; i++)
		z->keys[i] = y->keys[t + i];

	if (y->leaf == 0)//inner,内节点
	{
		for (i = 0; i < t; i++)
			z->childrens[i] = y->childrens[t + i];
	}

	y->num = t-1;

	// 移动、插入结点
	for (i = x->num; i >= idx + 1; i--)
	{
		x->childrens[i + 1] = x->childrens[i];
	}
	x->childrens[idx + 1] = z;

	// key 交换
	for (i = x->num-1; i >= idx; i--)
	{
		x->keys[i + 1] = x->keys[i];
	}
	x->keys[idx] = y->keys[t-1];
	x->num += 1;
}

/*************************分裂 split end*****************************/

// 创建根结点
void btree_create(btree *T, int t) {
	T->t = t;

	btree_node *x = btree_create_node(t, 1);
	T->root = x;

}


void btree_insert_nonfull(btree *T, btree_node *x, KEY_VALUE k) {

	int i = x->num - 1;

	if (x->leaf == 1) {

		while (i >= 0 && x->keys[i] > k) {
			x->keys[i + 1] = x->keys[i];
			i--;
		}
		x->keys[i + 1] = k;
		x->num += 1;

	}
	else {
		while (i >= 0 && x->keys[i] > k) i--;

		if (x->childrens[i + 1]->num == (2 * (T->t)) - 1) {
			btree_split_child(T, x, i + 1);
			if (k > x->keys[i + 1]) i++;
		}

		btree_insert_nonfull(T, x->childrens[i + 1], k);
	}
}

void btree_insert(btree *T, KEY_VALUE key) {

	btree_node *r = T->root;

	if (r->num == 2 * T->t - 1) {

		btree_node *node = btree_create_node(T->t, 0);
		T->root = node;

		node->childrens[0] = r;

		btree_split_child(T, node, 0);

		int i = 0;
		if (node->keys[0] < key) i++;
		btree_insert_nonfull(T, node->childrens[i], key);

	}
	else {
		btree_insert_nonfull(T, r, key);
	}
}

/*************************合并 merge*****************************/
void btree_merge(btree *T, btree_node *x, int idx)
{
	btree_node *left = x->childrens[idx];
	btree_node *right = x->childrens[idx + 1];

	int i = 0;

	// 合并keys
	left->keys[T->t-1] = x->keys[idx];
	for (i = 0; i < T->t-1; i++)
	{
		left->keys[T->t + i] = right->keys[i];
	}

	// 如果不是子树，需要拷贝结点
	if (!left->leaf) {
		for (i = 0; i < T->t; i++) {
			left->childrens[T->t + i] = right->childrens[i];
		}
	}
	left->num += T->t;

	btree_destroy_node(right);

	// x 的key前移
	for (i = idx + 1; i < x->num; i++)
	{
		x->keys[i - 1] = x->keys[i];
		x->childrens[i] = x->childrens[i + 1];
	}

	x->childrens[i + 1] = NULL;
	x->num -= 1;

	if (x->num == 0) {
		T->root = left;
		btree_destroy_node(x);
	}
}

void btree_delete_key(btree *T, btree_node *node, KEY_VALUE key) {

	if (node == NULL) return;

	int idx = 0, i;

	while (idx < node->num && key > node->keys[idx]) {
		idx++;
	}

	if (idx < node->num && key == node->keys[idx]) {

		if (node->leaf) {

			for (i = idx; i < node->num - 1; i++) {
				node->keys[i] = node->keys[i + 1];
			}

			node->keys[node->num - 1] = 0;
			node->num--;

			if (node->num == 0) { //root
				free(node);
				T->root = NULL;
			}

			return;
		}
		else if (node->childrens[idx]->num >= T->t) {

			btree_node *left = node->childrens[idx];
			node->keys[idx] = left->keys[left->num - 1];

			btree_delete_key(T, left, left->keys[left->num - 1]);

		}
		else if (node->childrens[idx + 1]->num >= T->t) {

			btree_node *right = node->childrens[idx + 1];
			node->keys[idx] = right->keys[0];

			btree_delete_key(T, right, right->keys[0]);

		}
		else {

			btree_merge(T, node, idx);
			btree_delete_key(T, node->childrens[idx], key);

		}

	}
	else {

		btree_node *child = node->childrens[idx];
		if (child == NULL) {
			printf("Cannot del key = %d\n", key);
			return;
		}

		if (child->num == T->t - 1) {

			btree_node *left = NULL;
			btree_node *right = NULL;
			if (idx - 1 >= 0)
				left = node->childrens[idx - 1];
			if (idx + 1 <= node->num)
				right = node->childrens[idx + 1];

			if ((left && left->num >= T->t) ||
				(right && right->num >= T->t)) {

				int richR = 0;
				if (right) richR = 1;
				if (left && right) richR = (right->num > left->num) ? 1 : 0;

				if (right && right->num >= T->t && richR) { //borrow from next
					child->keys[child->num] = node->keys[idx];
					child->childrens[child->num + 1] = right->childrens[0];
					child->num++;

					node->keys[idx] = right->keys[0];
					for (i = 0; i < right->num - 1; i++) {
						right->keys[i] = right->keys[i + 1];
						right->childrens[i] = right->childrens[i + 1];
					}

					right->keys[right->num - 1] = 0;
					right->childrens[right->num - 1] = right->childrens[right->num];
					right->childrens[right->num] = NULL;
					right->num--;

				}
				else { //borrow from prev

					for (i = child->num; i > 0; i--) {
						child->keys[i] = child->keys[i - 1];
						child->childrens[i + 1] = child->childrens[i];
					}

					child->childrens[1] = child->childrens[0];
					child->childrens[0] = left->childrens[left->num];
					child->keys[0] = node->keys[idx - 1];

					child->num++;

					node->keys[idx - 1] = left->keys[left->num - 1];
					left->keys[left->num - 1] = 0;
					left->childrens[left->num] = NULL;
					left->num--;
				}

			}
			else if ((!left || (left->num == T->t - 1))
				&& (!right || (right->num == T->t - 1))) {

				if (left && left->num == T->t - 1) {
					btree_merge(T, node, idx - 1);
					child = left;
				}
				else if (right && right->num == T->t - 1) {
					btree_merge(T, node, idx);
				}
			}
		}

		btree_delete_key(T, child, key);
	}

}


int btree_delete(btree *T, KEY_VALUE key) {
	if (!T->root) return -1;

	btree_delete_key(T, T->root, key);
	return 0;
}


/******************测试************************/

void btree_print(btree *T, btree_node *node, int layer)
{
	btree_node* p = node;
	int i;
	if (p) {
		printf("\nlayer = %d keynum = %d is_leaf = %d\n", layer, p->num, p->leaf);
		for (i = 0; i < node->num; i++)
			printf("%c ", p->keys[i]);
		printf("\n");
		layer++;
		for (i = 0; i <= p->num; i++)
			if (p->childrens[i])
				btree_print(T, p->childrens[i], layer);
	}
	else printf("the tree is empty\n");
}


int main() {
	btree T = { 0 };

	btree_create(&T, SUB_M);
	srand(48);

	int i = 0;
	char key[30] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	for (i = 0; i < 26; i++) {
		//key[i] = rand() % 1000;
		printf("%c ", key[i]);
		btree_insert(&T, key[i]);
	}

	btree_print(&T, T.root, 0);

	for (i = 0; i < 26; i++) {
		printf("\n---------------------------------\n");
		btree_delete(&T, key[25 - i]);
		//btree_traverse(T.root);
		btree_print(&T, T.root, 0);
	}
	return 0;
}
